{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## 第10章-隐马尔科夫模型(HMM)-导读\n",
    "\n",
    "&emsp;&emsp;隐马尔可夫模型(HMM)和条件随机场(CRF)都属于概率模型，这两个模型涉及到的随机变量个数都非常多，为了描述随机变量之间的关系（是不是独立的），需要借助一个很有用的工具——概率图模型，概率图模型分为有向图和无向图，隐马尔可夫模型用的就是有向图。\n",
    "\n",
    "### 概率图模型\n",
    "&emsp;&emsp;在有向图中，用$\\circ$（圆圈）表示随机变量，可以是一维的，也可以是多维的，既可以是离散随机变量，也可以是连续的，$\\circ$叫做结点，图是由结点和边构成的，在有向图中就是有向边，要描述$Y$受$X$影响的，就将$X$和$Y$连接起来，并用箭头描述从$X$指向$Y$的方向。  \n",
    "&emsp;&emsp;第9章EM算法中的掷硬币的例子，一共有3个硬币，观察到的只有两个结果，首先掷第1个硬币，以$\\pi$的概率正面向上，如果第1个硬币正面向上，就去掷第2个硬币，第2个硬币以$p$的概率出现正面向上，如果第1个硬币反面向上，在第2次的时候，就去掷第3个硬币，第3个硬币以$q$的概率出现正面向上。  \n",
    "&emsp;&emsp;对应到有向图中，$X$就是第1次掷硬币的结果$\\{0,1\\}$，第2次掷硬币的结果也是$\\{0,1\\}$，第2次掷硬币概率的参数是依赖第1次掷硬币结果的，第1个随机变量$X$会对$Y$产生影响，就可以用概率图来表示。  \n",
    "\n",
    "<br/><center><img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../../../PhaseFour/Note/image/10-1-GMM-Probabilistic-Graphica.jpg\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图10-1 高斯混合模型的概率图</div></center>  \n",
    "\n",
    "&emsp;&emsp;对应到EM算法的混合高斯模型，第1个随机变量$X$是一个离散的分布，它决定了是从第几个高斯模型中抽取变量，在GMM算法中，有$\\{1,2,\\cdots,K\\}$一共$K$个高斯分布。随机变量$Y$也是一个高斯分布$N(\\mu,\\sigma^2)$，高斯分布的参数取决于第1次随机变量$X$的取值。以上就是用两个结点和一条边表示高斯混合模型。  \n",
    "\n",
    "<br/><center><img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../../../PhaseFour/Note/image/10-2-NaiveBayes-Probabilistic-Graphica.jpg\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图10-2 朴素贝叶斯模型的概率图</div></center>   \n",
    "\n",
    "&emsp;&emsp;朴素贝叶斯模型的概率图如图10-2所示，$X$的分布是依赖于类别的，不同的类别，$X$的分布是不同的，在朴素贝叶斯中，当给定$Y$的值，$X$之间是相互独立的，所以只有$Y$到$X$的箭头，没有$X$之间的箭头。  \n",
    "&emsp;&emsp;一个箭头可以表示两个随机变量之间的关系，引入条件独立的概念，在概率图模型中，假设有三个随机变量$X,Y,Z$，之前讲的EM算法是含有隐变量和观测变量的，一般来说，隐变量在图模型中用圆$\\circ$表示，如果能观察到一个变量取值的时候，用带阴影的圆$\\bullet$表示。在掷硬币的例子中，第1个结果是观察不到的，用空心圆$\\circ$表示，第2个结果是可以观察到的，用带阴影的圆$\\bullet$表示。为什么要强调隐变量和观测变量，圆是空心还是阴影会影响到随机变量的依赖性。  \n",
    "\n",
    "<br/><center><img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../../../PhaseFour/Note/image/10-3-Relationship-between-Random-Variables-1.jpg\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图10-3 随机变量之间的关系(1)</div></center>\n",
    "\n",
    "&emsp;&emsp;图10-3中，随机变量都是空心圆，这三个随机变量都是观测不到的，可得$P(X,Z) \\neq P(X)(Z)$ \n",
    "\n",
    "<br/><center><img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../../../PhaseFour/Note/image/10-4-Relationship-between-Random-Variables-2.jpg\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图10-4 随机变量之间的关系(2)</div></center>\n",
    "  \n",
    "&emsp;&emsp;图10-4中，$Y$是带阴影的圆，随机变量$Y$是可以观察到的，可得$P(X,Z|Y)=P(X|Y)P(Z|Y)$，从箭头的指向看，信息是从$X$传到$Y$，$Y$传到$Z$，一旦将$Y$固定了，信息的流通相当于被$Y$观察到的值堵住了，所以当观察到$Y$时，$X$和$Z$就是独立的。 \n",
    "\n",
    "<br/><center><img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../../../PhaseFour/Note/image/10-5-Relationship-between-Random-Variables-3.jpg\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图10-5 随机变量之间的关系(3)</div></center>\n",
    "\n",
    "&emsp;&emsp;图10-5中，$Y$指向了两边，这个时候单看$X$和$Z$是不独立的，满足$P(X,Z) \\neq P(X)P(Z)$，如果给定$Y$，$X$和$Z$是独立的，满足$P(X,Z|Y)=P(X|Y)P(Z|Y)$\n",
    "\n",
    "<br/><center><img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../../../PhaseFour/Note/image/10-6-Relationship-between-Random-Variables-4.jpg\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图10-6 随机变量之间的关系(4)</div></center>\n",
    "\n",
    "&emsp;&emsp;图10-6中，随机变量满足$P(X,Z)=P(X)P(Z),P(X,Z|Y)\\neq P(X|Y)P(Z|Y)$\n",
    "\n",
    "### 隐马尔可夫模型的基本概念\n",
    "> 变量多，用概率图模型（有向图）表示变量间的关系。  \n",
    "模型参数及符号：状态集合，状态转移概率矩阵，观测集合，观测概率矩阵\n",
    "，初始状态概率向量\n",
    "\n",
    "#### 隐马尔可夫模型的定义\n",
    "<br/><center><img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../../../PhaseFour/Note/image/10-7-HMM-Probabilistic-Graphica-Model.jpg\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图10-7 隐马尔可夫概率图模型</div></center>  \n",
    "\n",
    "&emsp;&emsp;图10-7是隐马尔可夫模型的概率图模型，如果单看上面一行，是马尔可夫链，因为上面一行都是空心圆（观察不到的隐变量），故称为隐马尔可夫模型。上面这一行观察不到的变量集合称为**状态序列**，下面一行观测到的变量集合称为**观测序列**。状态序列记为$(i_1,i_2,\\cdots,i_t,i_{t+1},i_{T-1},i_T)$，观测序列记为$(o_1,o_2,\\cdots,o_t,o_{t+1},\\cdots,o_{T-1},o_T)$  \n",
    "&emsp;&emsp;隐马尔可夫模型的特点，已知第1个状态变量$i_1$，$i_1$会影响第2个状态变量$i_2$，同时也会影响观测变量$o_1$，当得到第2个状态变量$i_2$，会影响状态变量$i_3$，也会影响第2个观测变量$o_2$，依次递推。隐马尔可夫模型从状态变量看是一个影响一个的，可以理解成时间序列模型，其适用范围为文本分析，比如标注问题。  \n",
    "&emsp;&emsp;已知$i_t \\in \\{q_1,q_2,\\cdots,q_N\\}, o_t \\in \\{v_1,v_2,\\cdots,v_M\\}$，其中N是可能的状态数，M是可能的观测数。状态序列为$I=(i_1,i_2,\\cdots,i_T)$，观测序列为$O=(o_1,o_2,\\cdots,o_T)$，现考虑状态与观测之间、状态与状态之间的关系。\n",
    "\n",
    "##### 状态与状态之间的关系 \n",
    "$$\\begin{array}{cc}\n",
    "{} & i_2=q_1 & i_2=q_2 & \\cdots & i_2=q_N \\\\\n",
    "i_1=q_1 & a_{11} & a_{12} & \\cdots & a_{1N} \\\\\n",
    "i_1=q_2 & a_{21} & a_{22} & \\cdots & a_{2N} \\\\\n",
    "\\vdots & \\vdots & \\vdots & \\cdots & vdots \\\\\n",
    "i_1=q_N & a_{N1} & a_{N2} & \\cdots & a_{NN}\n",
    "\\end{array}$$所以$\\displaystyle a_{ij} = P(i_2=q_j|i_1=q_i)，\\sum_{i=1}^N a_{1i} = 1$  \n",
    "$A$为状态转移概率矩阵：$$A_{N \\times N} = \\left[\\begin{array}{cc}\n",
    "a_{11} & a_{12} & \\cdots & a_{1N} \\\\\n",
    "a_{21} & a_{22} & \\cdots & a_{2N} \\\\\n",
    "& &\\vdots \\\\\n",
    "a_{N1} & a_{N2} & \\cdots & a_{NN}\n",
    "\\end{array}\\right]$$&emsp;&emsp;这里给出的是$i_1$与$i_2$之间的关系，在马尔可夫模型假设中，这个关系不随时间$t$而变化，也就是说$i_1$和$i_2$之间的关系可以用这个矩阵表示，$i_2$和$i_3$之前的关系也可以用这个矩阵表示。  \n",
    "\n",
    "##### 状态与观测之间的关系\n",
    "$$\\begin{array}{cc}\n",
    "{} & o_1=v_1 & o_1=v_2 & \\cdots & o_1=v_M \\\\\n",
    "i_1=q_1 & b_1(1) & b_1(2) & \\cdots & b_1(M) \\\\\n",
    "i_1=q_2 & b_2(1) & b_2(2) & \\cdots & b_2(M) \\\\\n",
    "\\vdots & \\vdots & \\vdots & \\cdots & vdots \\\\\n",
    "i_1=q_N & b_N(1) & b_N(2) & \\cdots & b_N(M)\n",
    "\\end{array}$$，其中$\\displaystyle \\sum_{i=1}^M b_1(i) = 1$  \n",
    "$B$为观测概率矩阵：$$B_{N \\times M} = \\left[\\begin{array}{cc}\n",
    "b_1(1) & b_1(2) & \\cdots & b_1(M) \\\\\n",
    "b_2(1) & b_2(2) & \\cdots & b_2(M) \\\\\n",
    "& &\\vdots \\\\\n",
    "b_N(1) & b_N(2) & \\cdots & b_N(M)\n",
    "\\end{array}\\right]$$  \n",
    "\n",
    "##### 初始状态概率\n",
    "&emsp;&emsp;对于整个模型的参数，就差第1部分——初始状态概率，已知$i_1 \\in \\{q_1,q_2,\\cdots,q_N\\}$将每一个的概率都用$\\pi_n$表示：$$\\begin{array}{l} \n",
    "\\pi_1=P(i_1=q_1) \\\\\n",
    "\\pi_2=P(i_1=q_2) \\\\\n",
    "\\vdots \\\\\n",
    "\\pi_N=P(i_1=q_N)\n",
    "\\end{array}$$最后，令$\\pi=(\\pi_1,\\pi_2,\\cdots,\\pi_N)$  \n",
    "\n",
    "&emsp;&emsp;在整个隐马尔可夫模型中，参数由初始状态概率向量$\\pi$，状态转移概率矩阵$A$和观测概率矩阵$B$组成，即$\\lambda=(\\pi,A,B)$，其中$\\pi$中的参数有N个，$A$中的参数有$N \\times N$个，$B$中的参数有$N \\times M$个，其中自由参数有多少个？$\\pi$中的自由参数为$N-1$个（$N$个参数，1个约束条件），$A$中的自由参数为$N \\times N - N$个，$B$中的自由参数为$N \\times M - M$个。  \n",
    "\n",
    "#### 两个基本假设\n",
    "1. 齐次马尔可夫性假设：指的是隐变量之间的关系，在任意时刻$t$，隐变量的取值只与前一时刻状态的取值有关，与其他时刻的状态无关，用公式表示为$$P(i_t|i_{t-1},\\cdots,i_1)=P(i_t|i_{t-1})$$\n",
    "2. 观测独立性假设：指的是隐变量和观测变量之间的关系，在任意时刻的观测只依赖于该时刻的马尔可夫链的状态，与其他观测及状态无关，用公式表示为$$P(o_t|i_T,o_T,i_{T-1},o_{T-1},\\cdots,i_{t+1},o_{t+1},i_t,o_t,\\cdots,i_1,o_1)=P(o_t|i_t)$$  \n",
    "\n",
    "&emsp;&emsp;这两个基本假设在实际情况中并不是很合理，为什么要做这样的假设呢？其实和朴素贝叶斯是类似的，简化模型中变量的关系。\n",
    "\n",
    "#### 三个基本问题\n",
    "1. 概率计算问题：给定模型$\\lambda=(A,B,\\pi)$和观测序列$O=(o_1,o_2,\\cdots,o_T)$，计算在模型$\\lambda$下观测序列$O$出现的概率$P(O|\\lambda)$\n",
    "2. 学习问题：已知观测序列$O=(o_1,o_2,\\cdots,o_T)$，用极大似然估计的方法估计参数，即估计模型$\\lambda=(A,B,\\pi)$参数，使得在该模型下观测序列概率$P(O|\\lambda)$最大\n",
    "3. 预测问题：已知观测序列$O=(o_1,o_2,\\cdots,o_T)$，求给定观测序列条件概率$P(I|O)$最大的状态序列$I=(i_1,i_2,\\cdots,i_T)$，即给定观测序列，求最有可能的对应的状态序列  \n",
    "\n",
    "### 概率计算算法\n",
    "&emsp;&emsp;给定模型$\\lambda=(A,B,\\pi)$和观测序列$O=(o_1,o_2,\\cdots,o_T)$，计算在模型$\\lambda$下观测序列$O$出现的概率$P(O|\\lambda)$，书中一共提到了两个方法，实际上是三种：直接计算法、前向算法、后向算法。  \n",
    "\n",
    "#### 直接计算法\n",
    "$$\\begin{aligned} P(O|\\lambda) \n",
    "&= \\sum_I P(O|I,\\lambda)P(I|\\lambda) \\\\\n",
    "&= \\sum_{i_1,i_2,\\cdots,i_T} \\pi_{i_1}b_{i_1}(o_1)a_{i_1 i_2}b_{i_2}(o_2) \\cdots a_{i_{T-1} i_T}b_{i_T}(o_T)\n",
    "\\end{aligned}$$\n",
    "&emsp;&emsp;首先观察求和符号中$b$有$T$项，$a$有$T-1$项，$\\pi$有1项，一共有$2T$项，求和是从$i_1,i_2,\\cdots,i_T$不同的取值求和，对于$i_1$取值有$N$个，$i_2$取值有$N$个……$i_T$取值有$N$个，所以求和范围有$N^T$项，要对$N^T$个范围进行求和，每一个求和范围都需要$O(T)$个计算量，所以计算复杂度为$2T \\times N^T=2TN^T=O(TN^T)$。\n",
    "\n",
    "#### 前向算法\n",
    "> 算法10.2（观测序列概率的前向算法）\n",
    "输入：隐马尔可夫模型$\\lambda$，观测序列$O$  \n",
    "输出：观测序列概率$P(O|\\lambda)$  \n",
    "(1)初值：$\\alpha_1(i)=\\pi_i b_i(o_1), \\quad i=1,2,\\cdots,N$  \n",
    "(2)递推，对$t=1,2,\\cdots,T-1$，$$\\alpha_{t+1}(i)=\\left[\\sum_{j=1}^N \\alpha_t(j) a_{ji} \\right] b_i(o_t+1), \\quad i=1,2,\\cdots,N$$(3)终止$$P(O|\\lambda)=\\sum_{i=1}^N \\alpha_T(i)$$  \n",
    "\n",
    "<br/><center><img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../../../PhaseFour/Note/image/10-8-Forward-Algorithm-Probabilistic-Graphica.jpg\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图10-8 前向算法概率图</div></center>\n",
    "\n",
    "&emsp;&emsp;首先定义了$\\alpha_t(i)=P(o_1,o_2,\\cdots,o_t,i_t=q_i|\\lambda), i=1,2,\\cdots,N$，如图10-8中表示的就是虚线框中的联合概率分布， 然后通过递推的方式，一步一步得到$\\alpha_T(i)$，递推关系为$\\displaystyle \\alpha_{t+1}(i)=\\left[\\sum_{j=1}^N \\alpha_t(j) a_{ji} \\right] b_i(o_t+1)$，当$t=1$时，可以算出$\\alpha_1(1),\\alpha_1(2),\\cdots,\\alpha_1(i),\\cdots,\\alpha_1(N)$，当$t=2$时，根据递推可以计算出$\\alpha_2(1),\\alpha_2(2),\\cdots,\\alpha_2(i),\\cdots,\\alpha_2(N)$，同理可以一直递推到时刻$t=T$时，$\\alpha_T(1),\\alpha_T(2),\\cdots,\\alpha_T(i),\\cdots,\\alpha_T(N)$，最后计算$\\displaystyle P(O|\\lambda)=\\sum_{i=1}^N \\alpha_T(i)$。  \n",
    "&emsp;&emsp;首先每一时刻都要计算一列的$\\alpha$，一共有$T$个时刻，当计算每一列的时候，计算每一个$\\alpha_i$都用了前一个时刻$N$个不同的值，一共计算了$N$项，也就是$t$时刻计算了$N$项，每一个时刻都用了前一个时刻$N$个值，计算量为$N^2$，又有$T$个时刻，整个计算复杂度为$TN^2$\n",
    "\n",
    "#### 后向算法\n",
    "> 算法10.3（观测序列概率的后向算法）\n",
    "输入：隐马尔可夫模型$\\lambda$，观测序列$O$  \n",
    "输出：观测序列概率$P(O|\\lambda)$  \n",
    "(1)$\\beta_T(i)=1,\\quad i=1,2,\\cdots,N$  \n",
    "(2)对$t=T-1,T-2,\\cdots,1$，$$\\beta_t(i)=\\sum_{j=1}^N a_{ij}b_j(o_{t+1})\\beta_{t+1}(j), \\quad i=1,2,\\cdots,N$$(3)$$P(O|\\lambda)=\\sum_{i=1}^N \\pi_i b_i(o_1) \\beta_1(i)$$  \n",
    "\n",
    "<br/><center><img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../../../PhaseFour/Note/image/10-9-Backward-Algorithm-Probabilistic-Graphica.jpg\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图10-9 后向算法概率图</div></center>\n",
    "\n",
    "&emsp;&emsp;首先定义$\\beta_t(i)=P(o_{t+1},o_{t+2},\\cdots,o_T|i_t=q_i,\\lambda)$，如图10-9中表示的就是虚线框中的联合概率分布，对于每一个时刻$t$，$\\beta$一共有$N$个值，状态$i_t$的取值有$N$个，在后向算法中，首先计算最后一个时刻$t=T$时$(\\beta_T(1),\\beta_T(2),\\cdots,\\beta_T(N))$的取值，然后根据后面$N$个值的前一个时刻的值，以此类推，一共有$N$项求和，最后当给定$\\lambda$时，计算$P(O|\\lambda)$用$\\beta_1(i)$表示，此计算的复杂度和前向算法是一样的，计算复杂度为$T N^2$  \n",
    "\n",
    "### 学习算法\n",
    "&emsp;&emsp;本节和10.2节的过程是相反的，已知观测序列$O=(o_1,o_2,\\cdots,o_T)$，估计参数$\\lambda$。和之前讲过的很多模型是类似的，需要用一组训练数据集估计模型，之前可能是估计分类超平面，书中一共提到了两个方法：监督学习方法、Baum-Welch算法，这两种方法的区别在于哪个算法更贴近应用，这两个方法的学习设定是不一样的。  \n",
    "&emsp;&emsp;在隐马尔可夫模型中，能观察到的只是观测序列$O$，但是在监督学习方法中，人为地对观测值进行了标注$I$，所以状态序列$I$在该方法中也是已知的，这样不是很贴近现实情况。  \n",
    "\n",
    "#### 监督学习方法\n",
    "> &emsp;&emsp;假设已给训练数据包含S个长度相同的观测序列和对应的状态序列$\\{(O_1,I_1),(O_2,I_2),\\cdots,(O_S,I_S)\\}$，那么可以利用极大似然估计法来估计隐马尔可夫模型的参数。具体方法如下：  \n",
    "(1)转移概率$a_{ij}$的估计  \n",
    "设样本中时刻$t$处于状态$i$时刻$t+1$转移到状态$j$的频数为$A_{ij}$，那么状态转移概率$a_{ij}$的估计是$$\\hat{a}_{ij}=\\frac{A_{ij}}{\\displaystyle \\sum_{j=1}^N A_{ij}}, \\quad i=1,2,\\cdots,N; j=1,2,\\cdots,N$$(2)观测概率$b_j(k)$的估计  \n",
    "设样本中状态为$j$并观测为$k$的频数是$B_{jk}$，那么状态为$j$观测为$k$的概率$b_j(k)$的估计是$$\\hat{b}_j(k)=\\frac{B_{jk}}{\\displaystyle \\sum_{k=1}^M B_{jk}}, \\quad j=1,2,\\cdots,N;k=1,2,\\cdots,M$$(3)初始状态概率$\\pi_i$的估计$\\hat{\\pi}_i$为$S$个样本中初始状态为$q_i$的频率  \n",
    "\n",
    "观测序列和状态序列都有$S$个样本，需要估计的参数：  \n",
    "1. 首先初始状态$\\pi$，如果直接用极大似然估计，就是看这$S$个样本中在初始状态时的各个取值的频率。\n",
    "2. 概率转移矩阵$A$，前一个状态$i_t=q_i$，后一个状态$i_{t+1}=q_j$的概率记作$a_{ij}$，考察在$S$个观测序列中，每个观测序列都是有$(i_1,i_2,\\cdots,i_{T-1},i_T)$，一共有$S$个这样的马尔可夫链，总计$S(T-1)$组，在这些序列组中有多少是观测序列为$q_i$，然后在这些组中，又有多少组后一项的状态取值为$q_j$，这样的比例就是$a_{ij}$的估计。\n",
    "3. 观测概率$b_j(k)$的估计也是类似的。  \n",
    "\n",
    "#### Baum-Welch算法（EM算法）\n",
    "&emsp;&emsp;监督学习方法中，需要人为地标注每个观测值状态的取值，这样人工的工作量就会非常大，当不进行标注时，相当于模型中有$T$个隐变量和$T$个观测变量，当一个模型中既含有隐变量又含有观测变量时，估计模型的参数，很自然地想到用EM算法处理隐变量。Baum-Welch算法本质上就是EM算法，该算法的提出在EM算法之前，属于EM算法的特例。  \n",
    "&emsp;&emsp;EM算法已经在第9章介绍过了，需要求解完全数据的联合概率分步$P(O,I|\\lambda)$，然后极大化联合概率函数，为了计算简单取对数，$\\max \\ln P(O,I|\\lambda)$，使用迭代的方法更新参数$\\lambda=(\\pi,A,B)$，首先初始化$\\pi,A,B$，**E步：** 由于隐变量$i$的值未知，用给定的初值，在$\\ln P(O,I|\\lambda)$中所有包含隐变量的项用期望代替，**M步：** 最大化已经替换完的公式，利用拉格朗日乘子法，求解最优解。然后反复迭代，直到估计值收敛。算法10.4给出了EM算法在隐马尔可夫模型中的参数更新的递推式。  \n",
    "> 算法10.4（Baum-Welch算法）  \n",
    "输入：观测数据$O=(o_1,o_2,\\cdots,o_T)$  \n",
    "输出：隐马尔可夫模型  \n",
    "(1)初始化  \n",
    "对$n=0$，选取$a_{ij}^{(0)},b_j(k)^{(0)},\\pi_i^{(0)}$，得到模型$\\lambda^{(0)}=(A^{(0)},B^{(0)},\\pi^{(0)})$  \n",
    "(2)递推，对n=1,2,\\cdots,  \n",
    "$$a_{ij}^{(n+1)}=\\frac{\\displaystyle \\sum_{t=1}^{T-1} \\xi_t(i,j)}{\\displaystyle \\sum_{t=1}^{T-1} \\gamma_i(i)} \\\\\n",
    "b_j(k)^{(n+1)}=\\frac{\\displaystyle \\sum_{t=1,o_t=v_k}^T \\gamma_t(j)}{\\displaystyle \\sum_{t=1}^T \\gamma_t(j)} \\\\\n",
    "\\pi_i^{(n+1)} = \\gamma_1(i)\n",
    "$$其中$$\\displaystyle \\gamma_t(i)=\\frac{\\alpha_t(i)\\beta_t(i)}{P(O|\\lambda)}=\\frac{\\alpha_t(i)\\beta_t(i)}{\\displaystyle \\sum_{j=1}^N \\alpha_t(j)\\beta_t(j)} \\\\\n",
    "\\displaystyle \\xi_t(i,j)=\\frac{\\alpha_t(i)a_{ij}b_j(o_{t+1})\\beta_{t+1}(j)}{\\displaystyle \\sum_{i=1}^N \\sum_{j=1}^N \\alpha_t(i)a_{ij}b_j(o_{t+1})\\beta_{t+1}(j)}$$\n",
    "\n",
    "### 预测算法\n",
    "&emsp;&emsp;该算法其实就是一个标注问题，已知观测序列和模型参数$\\lambda$，让计算机标注每一个观测值的状态，书中提出了两个算法：近似算法（得到的结果并不是全局最优解）、维特比算法（用动态规划思想求最优路径）。\n",
    "\n",
    "#### 近似算法\n",
    "&emsp;&emsp;对每一个观测值进行标注并求解得出状态，实际上要求解的是使得$P(I|O,\\lambda)$概率最大的一组状态。  \n",
    "&emsp;&emsp;近似算法重新定义了一个函数$\\gamma_t(i)$，表示在时刻$t$处于状态$q_i$的概率：$$\\gamma_t(i)=P(i_t=q_i|O,\\lambda)$$&emsp;&emsp;近似算法的思路就是对于每一个时刻$t$都进行求解，当前这个时刻出现概率最大的状态$i_t^*=\\mathop{\\arg \\max} \\limits_{1 \\leqslant i \\leqslant N}\\left[\\gamma_t(i)\\right], t=1,2,\\cdots,T$，从而得到状态序列为$I^*=(i_1^*,i_2^*,\\cdots,i_T^*)$  \n",
    "&emsp;&emsp;这个算法的缺点很明显，求解每一个时刻$t$的最优状态时，都没有考虑该时刻和前一个时刻下状态之间的联系，有可能 会出现一种情况：相邻的两个状态之间的状态转移概率为0，这种情况说明得到的不是全局的最优解，但这种方法计算比较简单。  \n",
    "\n",
    "#### 维特比算法\n",
    "&emsp;&emsp;当求解最优路径时，可以采用维特比算法。以下用时刻$t_1,t_2,t_3$阐述这个算法的思想：在时刻$t_1$时，对应的状态变量为$i_1$，$i_1$可能的取值$q_1,q_2,\\cdots,q_N$有$N$个，在时刻$t_2$时，对应的状态变量为$i_2$，$i_2$可能的取值有$N$个，在时刻$t_3$时，对应的状态变量为$i_3$，$i_3$可能的取值有$N$个。  \n",
    "&emsp;&emsp;首先观察时刻$t=2$时，假设$i_2=q_1$，考察从前一时刻$t_1$到达$q_1$的路径的概率，从中选取概率最大的那个路径，假设是从$i_1=q_2$到$i_2=q_1$概率最大，就保留该路径，继续求解$i_2=q_2$时的$t_1$时刻到达$q_2$的概率最大的路径，假设是从$i_1=q_N$到$i_2=q_2$概率最大，就保留该路径，依次求取时刻$t=2$概率最大的最优路径。  \n",
    "&emsp;&emsp;考察完时刻$t=2$，再考察时刻$t=3$，求解当$i_3$取各个状态时的最优路径，此时不需要再看$t=2$之前的最优路径了，因为已经求解过了，只需要考察$t=3$的前一时刻的最优路径（即从$t=2$到$t=3$在各个状态的最优路径），已经记录了每一个状态之前的路径以及相应的概率值，用$\\delta(i)$表示，$i=1,2,\\cdots,N$。  \n",
    "&emsp;&emsp;所以当计算$i_3=q_1$的最优路径时，需要用的信息只有$\\delta(1),\\delta(2),\\cdots,\\delta(N)$、状态转移概率矩阵$A$，观测值$O$，观测概率矩阵$B$，在时刻$t=3$，一共计算了$N$个之前的最优路径，当计算完成之后，得到了$N$个最优路径以及相应的概率值，依次进行计算，完成后续时刻的最优路径计算，这样就完成了一个递推过程，这就是动态规划，也就是维特比算法的基本思想。\n",
    "\n",
    "> **算法10.5（维特比算法）**  \n",
    "输入：模型$\\lambda=(A,B,\\pi)$和观测$O=(o_1,o_2,\\cdots,o_T)$  \n",
    "输出：最优路径$I^*=(i_1^*,i_2^*,\\cdots,i_T^*)$  \n",
    "(1)初始化$$\\delta_1(i) = \\pi_i b_i(o_1),\\quad i=1,2,\\cdots,N \\\\\n",
    "\\psi_1(i)=0,\\quad i=1,2,\\cdots,N$$(2)递推，对$t=2, 3,\\cdots,T$\n",
    "$$\\delta_t(i)=\\mathop{\\max} \\limits_{1 \\leqslant j \\leqslant N}\\left[\\delta_{t-1}(j)a_{ji} \\right] b_i(o_t),\\quad i=1,2,\\cdots,N \\\\ \n",
    "\\psi_t(i) = \\mathop{\\arg \\max} \\limits_{1 \\leqslant j \\leqslant N} \\left[\\delta_{t-1}(j)a_{ji} \\right], \\quad i=1,2,\\cdots,N$$(3)终止$$P^*=\\mathop{\\max} \\limits_{1 \\leqslant i \\leqslant N} \\delta_T(i) \\\\\n",
    "i_T^*=\\mathop{\\max} \\limits_{1 \\leqslant i \\leqslant N} \\left[\\delta_T(i) \\right]$$(4)最优路径回溯，对$t=T-1,T-2,\\cdots,1$ $$i_t^*=\\psi_{t+1}(i_{t+1}^*)$$求得最优路径$I^*=(i_1^*,i_2^*,\\cdots,i_T^*)$.\n",
    "\n",
    "&emsp;&emsp;现考察最大化最优路径对应的最大化概率值是什么样的概率，在(2)步的递推，最大化的是$\\delta_t(i)$，书中给出了定义$\\delta_t(i)=\\mathop{\\max} \\limits_{i_1,i_2,\\cdots,i_t}P(i_t=i,i_{t-1},\\cdots,i_1,o_t,\\cdots,o_1|\\lambda)$，只固定了时刻$t$的状态值，然后最大化上述概率，求解使得该概率最大的前面$t-1$个时刻的状态变量的取值，但是预测算法的目标是$\\arg \\max P(I|O,\\lambda)$，这两个概率的最大化是等价的，因为用乘法公式可得$P(I,O)=P(O)P(O|I)$，可知$P(O)$与$I$无关，所以在$I$取不同值时，$P(O)$是不变的，所以$\\arg \\max P(I|O,\\lambda)$和$\\arg \\max P(I,O)$是等价的。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
